package com.Projects.Exam.demo5;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Handle {
	
/*
	给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。
	注意：必须确保程序的时间复杂度是o(log2n)，int[] nums = {5, 7, 7, 8, 8, 10}
*/
	
	public static void main(String[] args) {
		int target = 70;
		int[] nums = {5, 7, 7, 8, 8, 10};
		int[] arr = {isnums(nums, target, "left"), isnums(nums, target, "right")};
		System.out.print(Arrays.toString(arr) + "\t");
		
		Map<String, Integer> a = new HashMap<>();
		a.put("位置L", isnums(nums, target, "left"));
		a.put("位置R", isnums(nums, target, "right"));
		System.out.print(a);
		
	}
	
	// 二分查找法
	public static int isnums(int[] nums, int target, String flag) {
		int r = -1;
		if (nums.length == 0) return r;
		int start = 0, end = nums.length - 1;
		while (start <= end) {
			int i = (start + end) / 2;
			if (target > nums[i]) {
				start = i + 1;
			} else if (target < nums[i]) {
				end = i - 1;
			} else {
				if (flag.equals("left")) {
					r = i;
					end = i - 1;
				} else {
					r = i;
					start = i + 1;
				}
			}
		}
		return r;
	}
}
